/**
 * 338. 比特位计数
 */
public class CountBits {
    // 暴力解法
//    public int[] countBits(int n) {
//        int[] ret = new int[n + 1];
//        ret[0] = 0;
//        for (int i = 1; i <= n; i++) {
//            ret[i] = getBits(i);
//        }
//        return ret;
//    }

    // 动态规划-最高有效位
//    public int[] countBits(int n) {
//        int[] ret = new int[n + 1];
//        ret[0] = 0;
//        int maxBit = 0; // 存储最高有效位
//        for (int i = 1; i <= n; i++) {
//            if ((i & (i - 1)) == 0) {
//                maxBit = i;
//            }
//            ret[i] = ret[i - maxBit] + 1;
//        }
//        return ret;
//    }

    // 动态规划-最低有效位
//    public int[] countBits(int n) {
//        int[] ret = new int[n + 1];
//        ret[0] = 0;
//        for (int i = 1; i <= n; i++) {
//            // 如果是奇数的话最低位一定是零
//            ret[i] = ret[i >> 1] + (i & 1);
//        }
//        return ret;
//    }

    // 动态规划-最低设置位
    public int[] countBits(int n) {
        int[] ret = new int[n + 1];
//        ret[0] = 0; 不需要进行赋值，会自动为0
        for (int i = 1; i <= n; i++) {
            ret[i] = ret[i & (i - 1)] + 1;
        }
        return ret;
    }

    private int getBits(int x) {
        int count = 0;
        while (x > 0) {
            x &= (x - 1);
            count ++;
        }
        return count;
    }
}
